package com.zlsy.learning.leetcode.sort;

import java.util.Arrays;

/**
 * @author zhouliang
 * @date 2020/9/9 20:39
 */
public class CountingSort1 {

  public static void main(String[] args) {
    int[] a = new int[] {2, 5, 3, 0, 2, 3, 0, 3};
    int n = a.length;
    final int[] ints = countingSort(a, n);
    System.out.println(Arrays.toString(ints));
  }

  /**
   * 计数排序
   *
   * @param a A是数组
   * @param n N是数组的大小
   */
  private static int[] countingSort(int[] a, int n) {

    // c的长度为a数组的最大值减1
    int max = 0;
    for (int i = 0; i < n; i++) {
      if (max < a[i]) {
        max = a[i];
      }
    }

    // a的值即为c的index；
    int[] c = new int[max + 1];
    for (int i = 0; i < n; i++) {
      c[a[i]] = c[a[i]] + 1;
    }

    // 遍历c的值，每个值加上前面的值
    int count = 0;
    for (int i = 0; i < max + 1; i++) {
      count = c[i] + count;
      c[i] = count;
      // 可以简化为：c[i] = c[i - 1] + c[i];
    }

    // 创建一个R数组用来放排序后的值
    int[] r = new int[n];
    for (int i = n - 1; i > 0; i--) {
      // 取出原数组i位置的值
      int score = a[i];
      // 在c数组里面为这个index的值就是r数组的index
      int k = c[score];
      r[k - 1] = score;
      // c数组的这个值用掉之后就要排除掉
      c[score] = k - 1;
    }
    return r;
  }
}
